var quickSort = function (arr) {
    if (arr.length <= 1) { return arr; }
    let pivot = arr.pop(), left = [], right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return [...quickSort(left), pivot, ...quickSort(right)]
};

let ary = [7, 4, 1, 6, 3, 2, 5, 8, 9]
console.log(quickSort(ary));//[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

// 第二种方法

function quickS(arr,low,hight) {
    let key   = arr[low];
    let left  = low;
    let right = hight;

    while (left<right) {
        while(left<right&&arr[right]>key){
            right--
        }
        arr[left]= arr[right];
        while (left<right&&arr[left]<key) {
            left--
        }
        arr[right] = arr[left];
    }
    arr[left]   = key;//此时 low = height

    quickS(arr,low,left-1);
    quickS(arr,left+1,hight);
}


let a = [2,1,4,5,7,6,3];
console.log(quickS(a,0,a.length-1));

